Sorted Sequence Problems

First and Last position of element in Sorted array

Leetcode 34

as the sequence is sorted, so upper_bound will return the exact next greater element , so upperIndex - 1 gives the last occurance of the target_element

auto lower_boundIndex = lower_bound(v.begin(), v.end(), key) - v.begin();     /*  1st occurance of element || next strictly GREATER element || " == v.end() " */
auto upper_boundIndex = upper_bound(v.begin(), v.end(), key) - v.begin();     /*  next strictly GREATER element || " == v.end() " */

if (lower_boundIndex == upper_boundIndex)
{
/*
    as the `upper_bound` can never return the 'target' element' for it only returns the next greater element;
    so, (lower_bound == upper_bound) only when element DOESN'T EXIST as both return `== .end()` if no target_element present
*/
}

    cout << "First Occurance Index: " << lower_boundIndex << endl;    /* 1st occurance */


    cout << "Last Occurance Index: " << (upper_boundIndex - 1) << endl;   /*  ⏩ (upper_boundIndex - 1) to get LAST OCCURANCE of target_element */
    /* bcoz, in sorted sequence upper_bound gives NEXT GREATER ELEMENT means (target_index + 1),
    And as its SORTED so  all occurances of 'target_element' will be together and the next index will be the [greater element which upper_bound returns] so we do (upper_boundIndex - 1)
    */